package org.basis.algorithm.sort;

import org.basis.algorithm.common.SortUtil;

/**
 * 荷兰国旗问题
 *
 * @author Mr_wenpan@163.com 2021/12/06 11:04
 */
public class DutchFlagQuestion {

    public static void main(String[] args) {
        int[] arr = {1, 30, 22, 90, 20, 77, 33, 55, 66, 8, 5, 9, 3, 0, 10, 7, 2, 3, 9, 8, 2, 2, 5, 1, 2, 4, 5};
        process2(arr, 5);
        SortUtil.printArr(arr);
    }

    private static void process(int[] arr, int num) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int left = 0;
        int right = arr.length - 1;
        int index = 0;
        while (index <= right) {
            if (arr[index] < num) {
                // 和左区交换
                SortUtil.swap(index, left, arr);
                left++;
                index++;
            } else if (arr[index] == num) {
                // 不用交换，直接往前走
                index++;
            } else {
                // 这里index不能++，因为交换后不知道整个数是否仍然小于或等于num
                SortUtil.swap(index, right, arr);
                right--;
            }
        }

    }

    private static void process2(int[] arr, int num) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int left = -1;
        int right = arr.length;
        int index = 0;
        while (index < right) {
            if (arr[index] < num) {
                // 和左区交换
                SortUtil.swap(index++, ++left, arr);
            } else if (arr[index] == num) {
                // 不用交换，直接往前走
                index++;
            } else {
                // 这里index不能++，因为交换后不知道整个数是否仍然小于或等于num
                SortUtil.swap(index, --right, arr);
            }
        }

    }

    /**
     * 荷兰国旗问题练习
     */
    private static void process3(int[] arr, int num) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int l = -1;
        int r = arr.length - 1;
        int index = 0;
        while (index < r) {
            if (arr[index] < num) {
                SortUtil.swap(++l, index++, arr);
            } else if (arr[index] > num) {
                // 右区向左扩一个单位，这里index不能++
                SortUtil.swap(--l, index, arr);
            } else {
                // 相等情况直接向前走
                index++;
            }
        }
    }
}
